package com.Oct_SevenTeen;


/**
 * 437. 路径总和 III
 * 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 *
 * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/path-sum-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/17 19:21
 */

public class Solution437 {

    int count=0;
    long sum=0;

    public int pathSum(TreeNode root, int targetSum) {
        if (root==null) return 0;
        dfs(root,targetSum);
        pathSum(root.left,targetSum);
        pathSum(root.right, targetSum);
        return count;
    }

    void dfs(TreeNode root,int targetSum){
        if (root==null) return;
        sum+=root.val;
        if (sum==targetSum)
        {
            count++;
        }
        dfs(root.left,targetSum);
        dfs(root.right,targetSum);
        sum-=root.val;
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
}
